package com.ryujung.linked_list.leetCode_206;

/**
 * 链表反转
 */
public class Solution {
    /**链表反转
     * 
     * 双指针法
     * 时间复杂度:O(n)
     * 空间复杂度:O(1)
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode tempNext = cur.next;

            cur.next = pre;

            pre = cur;
            cur = tempNext;
        }
        return pre;
    }

    /**
     * 递归法
     * 思路:
     * 1.递归找到最后的元素,将最后的元素指向前一个元素
     * 2.将前一个元素指向null
     */
    public ListNode reverseListByResursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode p = reverseListByResursive(head.next);
        head.next.next = head; //将head元素的下一个元素,下方有错误写法和分析
        head.next = null;
        return p; //返回反转后的链表
    }
    /**
     * 做题的时候尝试将head.next.next=head;替换为p.next = head;
     * 测试结果只有最后一个元素指向第一个元素,做出如下分析:
     * p.next=head;在递归时会将p的next值一直做替换,导致链表中间的值全部被覆盖,
     * 而head.next.next=head;是将当前head值放在链表的尾部,递归调用时只会修改当前node的状态,
     * 也就是p的尾部的node的状态,而不会影响到最终返回值p
     */
}